import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {

    }
    //删除并获得点数
    public int deleteAndEarn(int[] nums) {
        int[] arr = new int[10001];
        for(int i=0;i<nums.length;i++) {
            arr[nums[i]]+=nums[i];
        }
        int[] f = new int[10001];
        int[] g = new int[10001];
        f[0] = arr[0];
        for(int i=1;i<=10000;i++) {
            f[i] = g[i-1] + arr[i];
            g[i] = Math.max(g[i-1],f[i-1]);
        }
        return Math.max(f[10000],g[10000]);
    }
    //全排列
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;
    public List<List<Integer>> permute(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];
        dfs(nums);
        return ret;
    }
    public void dfs(int[] nums) {
        if(path.size() == nums.length) {
            ret.add(new ArrayList(path));
            return;
        }
        for(int i=0;i<nums.length;i++) {
            if(check[i] == false) {
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                path.remove(path.size() - 1);
                check[i] = false;
            }
        }
    }
    //粉刷房子
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix[0].length;
        if(n==1) {
            return matrix[0][0];
        }
        //1.创造dp数组，dp[i][j]代表到这个点的最小路径和
        int[][] dp = new int[n][n];
        for(int i=0;i<n;i++) dp[0][i] = matrix[0][i];
        for(int i = 1;i<n;i++) {
            for(int j = 0;j<n;j++) {
                if(j-1>=0 && j+1<=n-1) {
                    dp[i][j] = matrix[i][j]+Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1]);
                }else if(j==n-1) {//右边界
                    dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j],dp[i-1][j-1]);
                }else {//左边界
                    dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j],dp[i-1][j+1]);
                }
            }
        }
        int min = dp[n-1][0];
        for(int i=1;i<n;i++) {
            if(dp[n-1][i] < min) min = dp[n-1][i];
        }
        return min;
    }

}
